package com.banmao.algorithm.No1To100.No15;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 *  我的题解
 */
public class Solution2 {

    public List<List<Integer>> threeSum(int[] nums) {

        // 原数组进行排序
        Arrays.sort(nums);

        ArrayList<List<Integer>> result = new ArrayList<>();

        // 遍历nums
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] > 0) {
                return result;
            }
            if(i > 0 && nums[i] == nums[i - 1]) {
                // 结果集对a去重
                continue;
            }

            // 初始化左右指针
            int left = i + 1;
            int right = nums.length - 1;

            // 循环只在右指针大于左指针时进行
            while (right > left) {
                int sum = nums[i] + nums[left] + nums[right];
                if(sum > 0) {
                    // 三数之和大于0，右指针收缩
                    right--;
                    continue;
                } else if (sum < 0) {
                    // 三数之和小于0，左指针收缩
                    left++;
                    continue;
                } else {
                    // 三数之和等于0，取结果
                    int a = nums[i], b = nums[left], c = nums[right];
                    ArrayList<Integer> temp = new ArrayList<>();
                    temp.add(a);
                    temp.add(b);
                    temp.add(c);
                    result.add(temp);
                }

                // 对结果集 b、c 进行去重
                while (left < right && nums[left] == nums[left + 1]) {
                    left++;
                }
                while (left < right && nums[right] == nums[right - 1]) {
                    right--;
                }

                left++;
                right--;
            }
        }
        return result;

    }

}
